package com.cuz.hot100;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Q23BracketGeneration {
    public static List<String> generateParenthesis1(int n) {
        if (n <= 0) {
            return Collections.emptyList();
        }
        List<String> res = new ArrayList<>();
        process(res, new StringBuilder("("), n - 1, n);
        return res;
    }

    public static void main(String[] args) {
        System.out.println(generateParenthesis1(2));
        System.out.println(generateParenthesis1(1));
        System.out.println(generateParenthesis1(3));
    }

    private static void process(List<String> res, StringBuilder temp, int left, int right) {
        if (left == 0 && right == 0) {
            res.add(temp.toString());
            return;
        }
        if (left == right) {
            temp.append("(");
            process(res, temp, left - 1, right);
            temp.deleteCharAt(temp.length() - 1);
        } else if (left < right) {
            if (left > 0) {
                temp.append("(");
                process(res, temp, left - 1, right);
                temp.deleteCharAt(temp.length() - 1);
            }
            temp.append(")");
            process(res, temp, left, right - 1);
            temp.deleteCharAt(temp.length() - 1);
        }

    }
}
